package main;

import java.util.Arrays;

public class xierSort {


        public static void main(String []args){
            int []arr ={1,4,2,7,9,8,3,6};
            sort(arr);
            System.out.println(Arrays.toString(arr));
            int []arr1 ={1,4,2,7,9,8,3,6};
            Shell(arr1);
            System.out.println(Arrays.toString(arr1));
        }

        /**
         * 希尔排序 针对有序序列在插入时采用交换法
         * @param arr
         */
        public static void sort(int []arr){
            //增量gap，并逐步缩小增量
            for(int gap = arr.length/2; gap>0 ; gap/=2){

                //从第gap个元素，逐个对其所在组进行直接插入排序操作

                for(int i=gap ; i<arr.length;i++){

                    int j = i;

                    while(j-gap>=0 && arr[j]<arr[j-gap]){
                        //插入排序采用交换法
                        swap(arr,j,j-gap);
                        j -= gap;
                    }
                }
            }
        }

        /**
         * 希尔排序 针对有序序列在插入时采用移动法。
         * @param array
         */
        public static int[] Shell( int[] array){

            int lenth = array.length ;
            int gap = lenth/2;
            int current;
            while(gap  > 0){
                for( int i = gap; i< lenth; i++){

                    // 保存变量     i=5
                    current = array[i];
                    // 保存索引     preIndex=0
                    int preIndex = i-gap;
                    // 大
                    while( preIndex>=0 && array[preIndex] > current ){
                        // 把 索引 0 的值=大的值赋给  索引为5的
                        array[preIndex + gap] = array[preIndex];
                        preIndex -= gap;     // preIndex =-5
                    }
                    // 再把current保存的 较小值 赋给索引为0的；
                    array[preIndex+gap] = current;
                }
                gap /=2;
            }
            return array;
        }
        /**
         * 交换数组元素
         * @param arr
         * @param a
         * @param b
         */
        public static void swap(int []arr,int a,int b){
            arr[a] = arr[a]+arr[b];
            arr[b] = arr[a]-arr[b];
            arr[a] = arr[a]-arr[b];
        }

}
